package study.datastructure.graph.kruskal;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-06-07 14:22
 */

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 2024/6/7,
 */


public class KruskalAlgorithm {
    //顶点的边数 顶点数
    int numVertex,numEdges;

    List<Edge> edges; //图的所有边

    public KruskalAlgorithm(int v,int e){
        this.numVertex=v;
        this.numEdges=e;

        edges=new ArrayList<>(numEdges);

    }

    // 向图中添加边
    public void addEdge(int src, int dest, int weight) {
        edges.add(new Edge(src, dest, weight));
    }

    //查找子集的根结点
    public int find(Subset[] subsets,int i){
        if(subsets[i].parent!=i){
            subsets[i].parent=find(subsets,subsets[i].parent); //递归查找到真正的根节点
        }
        return subsets[i].parent;
    }


    //联合两个子集
    public void union(Subset[] subsets,int x,int y){
        int xRoot=find(subsets,x);
        int yRoot=find(subsets,y);

        if (subsets[xRoot].rank>subsets[yRoot].rank){
            subsets[yRoot].parent=xRoot;
            //subsets[xRoot].rank++;
        } else if (subsets[xRoot].rank < subsets[yRoot].rank) {
            subsets[xRoot].parent=yRoot;
            //subsets[yRoot].rank++;
        }else {
            subsets[yRoot].parent=xRoot;
            subsets[xRoot].rank++;
        }
    }

    //kruskal 算法主函数

    public void kruskalMST(){
        //最小生成树
        List<Edge> result=new ArrayList<>();

        int numEdges=0;//生成边
        //按权重排序
        Collections.sort(edges, Comparator.comparingInt(o->o.weight));

        Subset[] subsets=new Subset[numVertex];

        for (int i = 0; i < numVertex; i++) {
            subsets[i]=new Subset(i,0); //初始化 秩都为0
        }

        //遍历所有的边 直到结果中的边数为numVertex-1
        for (int i = 0; numEdges<this.numVertex-1; i++) {
            Edge next_edge = edges.get(i);
            int srcRoot = find(subsets, next_edge.src);
            int destRoot = find(subsets, next_edge.dest);

            //如果两条边不构成环 就加入结果中
            if (srcRoot!=destRoot){
                result.add(next_edge);
                union(subsets,srcRoot,destRoot); //合成
                numEdges++;
            }

        }
    //打印生成树
        System.out.println("Following are the edges in the constructed MST by kruskal");
        for (Edge edge : result) {
            System.out.println(edge.src +"->"+edge.dest+".."+edge.weight);
        }


    }
    public static void main(String[] args) {
        int V = 4; // 图中的顶点数
        int E = 5; // 图中的边数
        KruskalAlgorithm graph = new KruskalAlgorithm(V, E);

        // 添加边
        graph.addEdge(0, 1, 10);
        graph.addEdge(0, 2, 6);
        graph.addEdge(0, 3, 5);
        graph.addEdge(1, 3, 15);
        graph.addEdge(2, 3, 4);

        // 运行Kruskal算法
        graph.kruskalMST();
    }





}
